home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 7: Sunsite / Linux Cubed Series 7 - Sunsite Vol 1.iso / system / network / manageme / tcpdump-.7 / tcpdump- / tcpdump-richard-1.7 / libpcap-0.0 / gencode.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-04-14  |  33.3 KB  |  1,793 lines
  1. /*
  2.  * Copyright (c) 1990, 1991, 1992, 1993, 1994
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that: (1) source code distributions
  7.  * retain the above copyright notice and this paragraph in its entirety, (2)
  8.  * distributions including binary code include the above copyright notice and
  9.  * this paragraph in its entirety in the documentation or other materials
  10.  * provided with the distribution, and (3) all advertising materials mentioning
  11.  * features or use of this software display the following acknowledgement:
  12.  * ``This product includes software developed by the University of California,
  13.  * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of
  14.  * the University nor the names of its contributors may be used to endorse
  15.  * or promote products derived from this software without specific prior
  16.  * written permission.
  17.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  18.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  19.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  20.  */
  21. #ifndef lint
  22. static char rcsid[] =
  23.     "@(#) $Header: gencode.c,v 1.55 94/06/20 19:07:53 leres Exp $ (LBL)";
  24. #endif
  25.  
  26. #include <sys/types.h>
  27. #include <sys/socket.h>
  28. #include <sys/time.h>
  29.  
  30. #include <net/if.h>
  31. #include <net/bpf.h>
  32.  
  33. #include <netinet/in.h>
  34. #include <netinet/if_ether.h>
  35.  
  36. #include <memory.h>
  37. #include <pcap.h>
  38. #include <pcap-namedb.h>
  39. #include <setjmp.h>
  40. #if __STDC__
  41. #include <stdarg.h>
  42. #include <stdlib.h>
  43. #else
  44. #include <varargs.h>
  45. #endif
  46.  
  47. #include "gencode.h"
  48.  
  49. #ifndef __GNUC__
  50. #define inline
  51. #endif
  52.  
  53. #ifndef ETHERTYPE_REVARP
  54. #define ETHERTYPE_REVARP    0x8035
  55. #endif
  56. #ifndef    ETHERTYPE_MOPDL
  57. #define    ETHERTYPE_MOPDL        0x6001
  58. #endif
  59. #ifndef    ETHERTYPE_MOPRC
  60. #define    ETHERTYPE_MOPRC        0x6002
  61. #endif
  62. #ifndef    ETHERTYPE_DN
  63. #define    ETHERTYPE_DN        0x6003
  64. #endif
  65. #ifndef    ETHERTYPE_LAT
  66. #define    ETHERTYPE_LAT        0x6004
  67. #endif
  68.  
  69. #define JMP(c) ((c)|BPF_JMP|BPF_K)
  70.  
  71. static jmp_buf top_ctx;
  72. static pcap_t *bpf_pcap;
  73.  
  74. /* VARARGS */
  75. volatile void
  76. #if __STDC__ || defined(SOLARIS)
  77. bpf_error(char *fmt, ...)
  78. #else
  79. bpf_error(fmt, va_alist)
  80.     char *fmt;
  81.     va_dcl
  82. #endif
  83. {
  84.     va_list ap;
  85.  
  86. #if __STDC__
  87.     va_start(ap, fmt);
  88. #else
  89.     va_start(ap);
  90. #endif
  91.     if (bpf_pcap != NULL)
  92.         (void)vsprintf(pcap_geterr(bpf_pcap), fmt, ap);
  93.     va_end(ap);
  94.     longjmp(top_ctx, 1);
  95.     /* NOTREACHED */
  96. }
  97.  
  98. static void init_linktype(int);
  99.  
  100. static int alloc_reg(void);
  101. static void free_reg(int);
  102.  
  103. static struct block *root;
  104.  
  105. /*
  106.  * We divy out chunks of memory rather than call malloc each time so
  107.  * we don't have to worry about leaking memory.  It's probably
  108.  * not a big deal if all this memory was wasted but it this ever
  109.  * goes into a library that would probably not be a good idea.
  110.  */
  111. #define NCHUNKS 16
  112. #define CHUNK0SIZE 1024
  113. struct chunk {
  114.     u_int n_left;
  115.     void *m;
  116. };
  117.  
  118. static struct chunk chunks[NCHUNKS];
  119. static int cur_chunk;
  120.  
  121. static void *newchunk(u_int);
  122. static void freechunks(void);
  123. static inline struct block *new_block(int);
  124. static inline struct slist *new_stmt(int);
  125. static struct block *gen_retblk(int);
  126. static inline void syntax(void);
  127.  
  128. static void backpatch(struct block *, struct block *);
  129. static void merge(struct block *, struct block *);
  130. static struct block *gen_cmp(u_int, u_int, long);
  131. static struct block *gen_mcmp(u_int, u_int, long, u_long);
  132. static struct block *gen_bcmp(u_int, u_int, u_char *);
  133. static struct block *gen_uncond(int);
  134. static inline struct block *gen_true(void);
  135. static inline struct block *gen_false(void);
  136. static struct block *gen_linktype(int);
  137. static struct block *gen_hostop(u_long, u_long, int, int, u_int, u_int);
  138. static struct block *gen_ehostop(u_char *, int);
  139. #ifdef FDDI
  140. static struct block *gen_fhostop(u_char *, int);
  141. #endif
  142. static struct block *gen_dnhostop(u_long, int, u_int);
  143. static struct block *gen_host(u_long, u_long, int, int);
  144. static struct block *gen_gateway(u_char *, u_long **, int, int);
  145. static struct block *gen_ipfrag(void);
  146. static struct block *gen_portatom(int, long);
  147. struct block *gen_portop(int, int, int);
  148. static struct block *gen_port(int, int, int);
  149. static int lookup_proto(char *, int);
  150. static struct block *gen_proto(int, int, int);
  151. static u_long net_mask(u_long *);
  152. static u_long net_mask(u_long *);
  153. static struct slist *xfer_to_x(struct arth *);
  154. static struct slist *xfer_to_a(struct arth *);
  155. static struct block *gen_len(int, int);
  156.  
  157. static void *
  158. newchunk(n)
  159.     u_int n;
  160. {
  161.     struct chunk *cp;
  162.     int k, size;
  163.  
  164.     /* XXX Round up to nearest long. */
  165.     n = (n + sizeof(long) - 1) & ~(sizeof(long) - 1);
  166.  
  167.     cp = &chunks[cur_chunk];
  168.     if (n > cp->n_left) {
  169.         ++cp, k = ++cur_chunk;
  170.         if (k >= NCHUNKS)
  171.             bpf_error("out of memory");
  172.         size = CHUNK0SIZE << k;
  173.         cp->m = (void *)malloc(size);
  174.         memset((char *)cp->m, 0, size);
  175.         cp->n_left = size;
  176.         if (n > size)
  177.             bpf_error("out of memory");
  178.     }
  179.     cp->n_left -= n;
  180.     return (void *)((char *)cp->m + cp->n_left);
  181. }
  182.  
  183. static void
  184. freechunks()
  185. {
  186.     int i;
  187.  
  188.     for (i = 0; i < NCHUNKS; ++i)
  189.         if (chunks[i].m)
  190.             free(chunks[i].m);
  191. }
  192.  
  193. /*
  194.  * A strdup whose allocations are freed after code generation is over.
  195.  */
  196. char *
  197. sdup(s)
  198.     char *s;
  199. {
  200.     int n = strlen(s) + 1;
  201.     char *cp = newchunk(n);
  202.     strcpy(cp, s);
  203.     return (cp);
  204. }
  205.  
  206. static inline struct block *
  207. new_block(code)
  208.     int code;
  209. {
  210.     struct block *p;
  211.  
  212.     p = (struct block *)newchunk(sizeof(*p));
  213.     p->s.code = code;
  214.     p->head = p;
  215.  
  216.     return p;
  217. }
  218.  
  219. static inline struct slist *
  220. new_stmt(code)
  221.     int code;
  222. {
  223.     struct slist *p;
  224.  
  225.     p = (struct slist *)newchunk(sizeof(*p));
  226.     p->s.code = code;
  227.  
  228.     return p;
  229. }
  230.  
  231. static struct block *
  232. gen_retblk(v)
  233.     int v;
  234. {
  235.     struct block *b = new_block(BPF_RET|BPF_K);
  236.  
  237.     b->s.k = v;
  238.     return b;
  239. }
  240.  
  241. static inline void
  242. syntax()
  243. {
  244.     bpf_error("syntax error in filter expression");
  245. }
  246.  
  247. static u_long netmask;
  248. static int snaplen;
  249.  
  250. int
  251. pcap_compile(pcap_t *p, struct bpf_program *program,
  252.          char *buf, int optimize, u_long mask)
  253. {
  254.     extern int n_errors;
  255.     int len;
  256.  
  257.     bpf_pcap = p;
  258.     if (setjmp(top_ctx))
  259.         return (-1);
  260.  
  261.     netmask = mask;
  262.     snaplen = pcap_snapshot(p);
  263.  
  264.     lex_init(buf ? buf : "");
  265.     init_linktype(pcap_datalink(p));
  266.     pcap_parse();
  267.  
  268.     if (n_errors)
  269.         syntax();
  270.  
  271.     if (root == NULL)
  272.         root = gen_retblk(snaplen);
  273.  
  274.     if (optimize) {
  275.         bpf_optimize(&root);
  276.         if (root == NULL ||
  277.             (root->s.code == (BPF_RET|BPF_K) && root->s.k == 0))
  278.             bpf_error("expression rejects all packets");
  279.     }
  280.     program->bf_insns = icode_to_fcode(root, &len);
  281.     program->bf_len = len;
  282.  
  283.     freechunks();
  284.     return (0);
  285. }
  286.  
  287. int
  288. pcap_compile_offline(char *buf, struct bpf_program *program,
  289.                         int optimize, int type, u_long mask, int snap)
  290. {
  291.     extern int n_errors;
  292.     int len;
  293.  
  294.     bpf_pcap = NULL;
  295.     if (setjmp(top_ctx))
  296.         return (-1);
  297.  
  298.     netmask = mask;
  299.     snaplen = snap;
  300.  
  301.     lex_init(buf ? buf : "");
  302.     init_linktype(type);
  303.     pcap_parse();
  304.  
  305.     if (n_errors)
  306.         syntax();
  307.  
  308.     if (root == NULL)
  309.         root = gen_retblk(snaplen);
  310.  
  311.     if (optimize) {
  312.         bpf_optimize(&root);
  313.         if (root == NULL ||
  314.             (root->s.code == (BPF_RET|BPF_K) && root->s.k == 0))
  315.             bpf_error("expression rejects all packets");
  316.     }
  317.     program->bf_insns = icode_to_fcode(root, &len);
  318.     program->bf_len = len;
  319.  
  320.     freechunks();
  321.     return (0);
  322. }
  323.  
  324. /*
  325.  * Backpatch the blocks in 'list' to 'target'.  The 'sense' field indicates
  326.  * which of the jt and jf fields has been resolved and which is a pointer
  327.  * back to another unresolved block (or nil).  At least one of the fields
  328.  * in each block is already resolved.
  329.  */
  330. static void
  331. backpatch(list, target)
  332.     struct block *list, *target;
  333. {
  334.     struct block *next;
  335.  
  336.     while (list) {
  337.         if (!list->sense) {
  338.             next = JT(list);
  339.             JT(list) = target;
  340.         } else {
  341.             next = JF(list);
  342.             JF(list) = target;
  343.         }
  344.         list = next;
  345.     }
  346. }
  347.  
  348. /*
  349.  * Merge the lists in b0 and b1, using the 'sense' field to indicate
  350.  * which of jt and jf is the link.
  351.  */
  352. static void
  353. merge(b0, b1)
  354.     struct block *b0, *b1;
  355. {
  356.     register struct block **p = &b0;
  357.  
  358.     /* Find end of list. */
  359.     while (*p)
  360.         p = !((*p)->sense) ? &JT(*p) : &JF(*p);
  361.  
  362.     /* Concatenate the lists. */
  363.     *p = b1;
  364. }
  365.  
  366. void
  367. finish_parse(p)
  368.     struct block *p;
  369. {
  370.     backpatch(p, gen_retblk(snaplen));
  371.     p->sense = !p->sense;
  372.     backpatch(p, gen_retblk(0));
  373.     root = p->head;
  374. }
  375.  
  376. void
  377. gen_and(b0, b1)
  378.     struct block *b0, *b1;
  379. {
  380.     backpatch(b0, b1->head);
  381.     b0->sense = !b0->sense;
  382.     b1->sense = !b1->sense;
  383.     merge(b1, b0);
  384.     b1->sense = !b1->sense;
  385.     b1->head = b0->head;
  386. }
  387.  
  388. void
  389. gen_or(b0, b1)
  390.     struct block *b0, *b1;
  391. {
  392.     b0->sense = !b0->sense;
  393.     backpatch(b0, b1->head);
  394.     b0->sense = !b0->sense;
  395.     merge(b1, b0);
  396.     b1->head = b0->head;
  397. }
  398.  
  399. void
  400. gen_not(b)
  401.     struct block *b;
  402. {
  403.     b->sense = !b->sense;
  404. }
  405.  
  406. static struct block *
  407. gen_cmp(offset, size, v)
  408.     u_int offset, size;
  409.     long v;
  410. {
  411.     struct slist *s;
  412.     struct block *b;
  413.  
  414.     s = new_stmt(BPF_LD|BPF_ABS|size);
  415.     s->s.k = offset;
  416.  
  417.     b = new_block(JMP(BPF_JEQ));
  418.     b->stmts = s;
  419.     b->s.k = v;
  420.  
  421.     return b;
  422. }
  423.  
  424. static struct block *
  425. gen_mcmp(offset, size, v, mask)
  426.     u_int offset, size;
  427.     long v;
  428.     u_long mask;
  429. {
  430.     struct block *b = gen_cmp(offset, size, v);
  431.     struct slist *s;
  432.  
  433.     if (mask != 0xffffffff) {
  434.         s = new_stmt(BPF_ALU|BPF_AND|BPF_K);
  435.         s->s.k = mask;
  436.         b->stmts->next = s;
  437.     }
  438.     return b;
  439. }
  440.  
  441. static struct block *
  442. gen_bcmp(offset, size, v)
  443.     u_int offset, size;
  444.     u_char *v;
  445. {
  446.     struct block *b, *tmp;
  447.  
  448.     b = NULL;
  449.     while (size >= 4) {
  450.         u_char *p = &v[size - 4];
  451.         long w = (p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3];
  452.         tmp = gen_cmp(offset + size - 4, BPF_W, w);
  453.         if (b != NULL)
  454.             gen_and(b, tmp);
  455.         b = tmp;
  456.         size -= 4;
  457.     }
  458.     while (size >= 2) {
  459.         u_char *p = &v[size - 2];
  460.         long w = (p[0] << 8) | p[1];
  461.         tmp = gen_cmp(offset + size - 2, BPF_H, w);
  462.         if (b != NULL)
  463.             gen_and(b, tmp);
  464.         b = tmp;
  465.         size -= 2;
  466.     }
  467.     if (size > 0) {
  468.         tmp = gen_cmp(offset, BPF_B, (long)v[0]);
  469.         if (b != NULL)
  470.             gen_and(b, tmp);
  471.         b = tmp;
  472.     }
  473.     return b;
  474. }
  475.  
  476. /*
  477.  * Various code constructs need to know the layout of the data link
  478.  * layer.  These variables give the necessary offsets.  off_linktype
  479.  * is set to -1 for no encapsulation, in which case, IP is assumed.
  480.  */
  481. static u_int off_linktype;
  482. static u_int off_nl;
  483. static int linktype;
  484. #ifdef FDDI
  485. extern int fddipad;
  486. #endif
  487.  
  488. static void
  489. init_linktype(type)
  490.     int type;
  491. {
  492.     linktype = type;
  493.  
  494.     switch (type) {
  495.  
  496.     case DLT_EN10MB:
  497.         off_linktype = 12;
  498.         off_nl = 14;
  499.         return;
  500.  
  501.     case DLT_SLIP:
  502.         /*
  503.          * SLIP doesn't have a link level type.  The 16 byte
  504.          * header is hacked into our SLIP driver.
  505.          */
  506.         off_linktype = -1;
  507.         off_nl = 16;
  508.         return;
  509.  
  510.     case DLT_NULL:
  511.         off_linktype = -1;
  512.         off_nl = 0;
  513.         return;
  514.  
  515.     case DLT_PPP:
  516.         off_linktype = 2;
  517.         off_nl = 4;
  518.         return;
  519.  
  520. #ifdef FDDI
  521.     case DLT_FDDI:
  522.         /*
  523.          * FDDI doesn't really have a link-level type field.
  524.          * We assume that SSAP = SNAP is being used and pick
  525.          * out the encapsulated Ethernet type.
  526.          */
  527.         off_linktype = 19 + fddipad;
  528.         off_nl = 21 + fddipad;
  529.         return;
  530. #endif
  531.  
  532.     case DLT_IEEE802:
  533.         off_linktype = 20;
  534.         off_nl = 22;
  535.         return;
  536.     }
  537.     bpf_error("unknown data link type 0x%x", linktype);
  538.     /* NOTREACHED */
  539. }
  540.  
  541. static struct block *
  542. gen_uncond(rsense)
  543.     int rsense;
  544. {
  545.     struct block *b;
  546.     struct slist *s;
  547.  
  548.     s = new_stmt(BPF_LD|BPF_IMM);
  549.     s->s.k = !rsense;
  550.     b = new_block(JMP(BPF_JEQ));
  551.     b->stmts = s;
  552.  
  553.     return b;
  554. }
  555.  
  556. static inline struct block *
  557. gen_true()
  558. {
  559.     return gen_uncond(1);
  560. }
  561.  
  562. static inline struct block *
  563. gen_false()
  564. {
  565.     return gen_uncond(0);
  566. }
  567.  
  568. static struct block *
  569. gen_linktype(proto)
  570.     int proto;
  571. {
  572.     switch (linktype) {
  573.     case DLT_SLIP:
  574.         if (proto == ETHERTYPE_IP)
  575.             return gen_true();
  576.         else
  577.             return gen_false();
  578.  
  579.     case DLT_PPP:
  580.         if (proto == ETHERTYPE_IP)
  581.             proto = 0x0021;        /* XXX - need ppp.h defs */
  582.         break;
  583.     }
  584.     return gen_cmp(off_linktype, BPF_H, (long)proto);
  585. }
  586.  
  587. static struct block *
  588. gen_hostop(addr, mask, dir, proto, src_off, dst_off)
  589.     u_long addr;
  590.     u_long mask;
  591.     int dir, proto;
  592.     u_int src_off, dst_off;
  593. {
  594.     struct block *b0, *b1;
  595.     u_int offset;
  596.  
  597.     switch (dir) {
  598.  
  599.     case Q_SRC:
  600.         offset = src_off;
  601.         break;
  602.  
  603.     case Q_DST:
  604.         offset = dst_off;
  605.         break;
  606.  
  607.     case Q_AND:
  608.         b0 = gen_hostop(addr, mask, Q_SRC, proto, src_off, dst_off);
  609.         b1 = gen_hostop(addr, mask, Q_DST, proto, src_off, dst_off);
  610.         gen_and(b0, b1);
  611.         return b1;
  612.  
  613.     case Q_OR:
  614.     case Q_DEFAULT:
  615.         b0 = gen_hostop(addr, mask, Q_SRC, proto, src_off, dst_off);
  616.         b1 = gen_hostop(addr, mask, Q_DST, proto, src_off, dst_off);
  617.         gen_or(b0, b1);
  618.         return b1;
  619.  
  620.     default:
  621.         abort();
  622.     }
  623.     b0 = gen_linktype(proto);
  624.     b1 = gen_mcmp(offset, BPF_W, (long)addr, mask);
  625.     gen_and(b0, b1);
  626.     return b1;
  627. }
  628.  
  629. static struct block *
  630. gen_ehostop(eaddr, dir)
  631.     u_char *eaddr;
  632.     int dir;
  633. {
  634.     struct block *b0, *b1;
  635.  
  636.     switch (dir) {
  637.     case Q_SRC:
  638.         return gen_bcmp(6, 6, eaddr);
  639.  
  640.     case Q_DST:
  641.         return gen_bcmp(0, 6, eaddr);
  642.  
  643.     case Q_AND:
  644.         b0 = gen_ehostop(eaddr, Q_SRC);
  645.         b1 = gen_ehostop(eaddr, Q_DST);
  646.         gen_and(b0, b1);
  647.         return b1;
  648.  
  649.     case Q_DEFAULT:
  650.     case Q_OR:
  651.         b0 = gen_ehostop(eaddr, Q_SRC);
  652.         b1 = gen_ehostop(eaddr, Q_DST);
  653.         gen_or(b0, b1);
  654.         return b1;
  655.     }
  656.     abort();
  657.     /* NOTREACHED */
  658. }
  659.  
  660. #ifdef FDDI
  661. /*
  662.  * Like gen_ehostop, but for DLT_FDDI
  663.  */
  664. static struct block *
  665. gen_fhostop(eaddr, dir)
  666.     u_char *eaddr;
  667.     int dir;
  668. {
  669.     struct block *b0, *b1;
  670.  
  671.     switch (dir) {
  672.     case Q_SRC:
  673.         return gen_bcmp(6 + 1 + fddipad, 6, eaddr);
  674.  
  675.     case Q_DST:
  676.         return gen_bcmp(0 + 1 + fddipad, 6, eaddr);
  677.  
  678.     case Q_AND:
  679.         b0 = gen_fhostop(eaddr, Q_SRC);
  680.         b1 = gen_fhostop(eaddr, Q_DST);
  681.         gen_and(b0, b1);
  682.         return b1;
  683.  
  684.     case Q_DEFAULT:
  685.     case Q_OR:
  686.         b0 = gen_fhostop(eaddr, Q_SRC);
  687.         b1 = gen_fhostop(eaddr, Q_DST);
  688.         gen_or(b0, b1);
  689.         return b1;
  690.     }
  691.     abort();
  692.     /* NOTREACHED */
  693. }
  694. #endif
  695.  
  696. /*
  697.  * This is quite tricky because there may be pad bytes in front of the
  698.  * DECNET header, and then there are two possible data packet formats that
  699.  * carry both src and dst addresses, plus 5 packet types in a format that
  700.  * carries only the src node, plus 2 types that use a different format and
  701.  * also carry just the src node.
  702.  *
  703.  * Yuck.
  704.  *
  705.  * Instead of doing those all right, we just look for data packets with
  706.  * 0 or 1 bytes of padding.  If you want to look at other packets, that
  707.  * will require a lot more hacking.
  708.  *
  709.  * To add support for filtering on DECNET "areas" (network numbers)
  710.  * one would want to add a "mask" argument to this routine.  That would
  711.  * make the filter even more inefficient, although one could be clever
  712.  * and not generate masking instructions if the mask is 0xFFFF.
  713.  */
  714. static struct block *
  715. gen_dnhostop(addr, dir, base_off)
  716.     u_long addr;
  717.     int dir;
  718.     u_int base_off;
  719. {
  720.     struct block *b0, *b1, *b2, *tmp;
  721.     u_int offset_lh;    /* offset if long header is received */
  722.     u_int offset_sh;    /* offset if short header is received */
  723.  
  724.     switch (dir) {
  725.  
  726.     case Q_DST:
  727.         offset_sh = 1;    /* follows flags */
  728.         offset_lh = 7;    /* flgs,darea,dsubarea,HIORD */
  729.         break;
  730.  
  731.     case Q_SRC:
  732.         offset_sh = 3;    /* follows flags, dstnode */
  733.         offset_lh = 15;    /* flgs,darea,dsubarea,did,sarea,ssub,HIORD */
  734.         break;
  735.  
  736.     case Q_AND:
  737.         /* Inefficient because we do our Calvinball dance twice */
  738.         b0 = gen_dnhostop(addr, Q_SRC, base_off);
  739.         b1 = gen_dnhostop(addr, Q_DST, base_off);
  740.         gen_and(b0, b1);
  741.         return b1;
  742.  
  743.     case Q_OR:
  744.     case Q_DEFAULT:
  745.         /* Inefficient because we do our Calvinball dance twice */
  746.         b0 = gen_dnhostop(addr, Q_SRC, base_off);
  747.         b1 = gen_dnhostop(addr, Q_DST, base_off);
  748.         gen_or(b0, b1);
  749.         return b1;
  750.  
  751.     default:
  752.         abort();
  753.     }
  754.     b0 = gen_linktype(ETHERTYPE_DN);
  755.     /* Check for pad = 1, long header case */
  756.     tmp = gen_mcmp(base_off + 2, BPF_H,
  757.                 (long)ntohs(0x0681), (long)ntohs(0x07FF));
  758.     b1 = gen_cmp(base_off + 2 + 1 + offset_lh, BPF_H, (long)ntohs(addr));
  759.     gen_and(tmp, b1);
  760.     /* Check for pad = 0, long header case */
  761.     tmp = gen_mcmp(base_off + 2, BPF_B, (long)0x06, (long)0x7);
  762.     b2 = gen_cmp(base_off + 2 + offset_lh, BPF_H, (long)ntohs(addr));
  763.     gen_and(tmp, b2);
  764.     gen_or(b2, b1);
  765.     /* Check for pad = 1, short header case */
  766.     tmp = gen_mcmp(base_off + 2, BPF_H,
  767.                 (long)ntohs(0x0281), (long)ntohs(0x07FF));
  768.     b2 = gen_cmp(base_off + 2 + 1 + offset_sh, BPF_H, (long)ntohs(addr));
  769.     gen_and(tmp, b2);
  770.     gen_or(b2, b1);
  771.     /* Check for pad = 0, short header case */
  772.     tmp = gen_mcmp(base_off + 2, BPF_B, (long)0x02, (long)0x7);
  773.     b2 = gen_cmp(base_off + 2 + offset_sh, BPF_H, (long)ntohs(addr));
  774.     gen_and(tmp, b2);
  775.     gen_or(b2, b1);
  776.  
  777.     /* Combine with test for linktype */
  778.     gen_and(b0, b1);
  779.     return b1;
  780. }
  781.  
  782. static struct block *
  783. gen_host(addr, mask, proto, dir)
  784.     u_long addr;
  785.     u_long mask;
  786.     int proto;
  787.     int dir;
  788. {
  789.     struct block *b0, *b1;
  790.  
  791.     switch (proto) {
  792.  
  793.     case Q_DEFAULT:
  794.         b0 = gen_host(addr, mask, Q_IP, dir);
  795.         b1 = gen_host(addr, mask, Q_ARP, dir);
  796.         gen_or(b0, b1);
  797.         b0 = gen_host(addr, mask, Q_RARP, dir);
  798.         gen_or(b1, b0);
  799.         return b0;
  800.  
  801.     case Q_IP:
  802.         return gen_hostop(addr, mask, dir, ETHERTYPE_IP,
  803.                   off_nl + 12, off_nl + 16);
  804.  
  805.     case Q_RARP:
  806.         return gen_hostop(addr, mask, dir, ETHERTYPE_REVARP,
  807.                   off_nl + 14, off_nl + 24);
  808.  
  809.     case Q_ARP:
  810.         return gen_hostop(addr, mask, dir, ETHERTYPE_ARP,
  811.                   off_nl + 14, off_nl + 24);
  812.  
  813.     case Q_TCP:
  814.         bpf_error("'tcp' modifier applied to host");
  815.  
  816.     case Q_UDP:
  817.         bpf_error("'udp' modifier applied to host");
  818.  
  819.     case Q_ICMP:
  820.         bpf_error("'icmp' modifier applied to host");
  821.  
  822.     case Q_DECNET:
  823.         return gen_dnhostop(addr, dir, off_nl);
  824.  
  825.     case Q_LAT:
  826.         bpf_error("LAT host filtering not implemented");
  827.  
  828.     case Q_MOPDL:
  829.         bpf_error("MOPDL host filtering not implemented");
  830.  
  831.     case Q_MOPRC:
  832.         bpf_error("MOPRC host filtering not implemented");
  833.  
  834.     default:
  835.         abort();
  836.     }
  837.     /* NOTREACHED */
  838. }
  839.  
  840. static struct block *
  841. gen_gateway(eaddr, alist, proto, dir)
  842.     u_char *eaddr;
  843.     u_long **alist;
  844.     int proto;
  845.     int dir;
  846. {
  847.     struct block *b0 = NULL, *b1, *tmp;
  848.  
  849.     if (dir != 0)
  850.         bpf_error("direction applied to 'gateway'");
  851.  
  852.     switch (proto) {
  853.     case Q_DEFAULT:
  854.     case Q_IP:
  855.     case Q_ARP:
  856.     case Q_RARP:
  857.         if (linktype == DLT_EN10MB)
  858.             b0 = gen_ehostop(eaddr, Q_OR);
  859. #ifdef FDDI
  860.         else if (linktype == DLT_FDDI)
  861.             b0 = gen_fhostop(eaddr, Q_OR);
  862. #endif
  863.         else
  864.             bpf_error("'gateway' supported only on ethernet or FDDI");
  865.  
  866.         b1 = gen_host(**alist++, 0xffffffffL, proto, Q_OR);
  867.         while (*alist) {
  868.             tmp = gen_host(**alist++, 0xffffffffL, proto, Q_OR);
  869.             gen_or(b1, tmp);
  870.             b1 = tmp;
  871.         }
  872.         gen_not(b1);
  873.         gen_and(b0, b1);
  874.         return b1;
  875.     }
  876.     bpf_error("illegal modifier of 'gateway'");
  877.     /* NOTREACHED */
  878. }
  879.  
  880. struct block *
  881. gen_proto_abbrev(proto)
  882.     int proto;
  883. {
  884.     struct block *b0, *b1;
  885.  
  886.     switch (proto) {
  887.  
  888.     case Q_TCP:
  889.         b0 = gen_linktype(ETHERTYPE_IP);
  890.         b1 = gen_cmp(off_nl + 9, BPF_B, (long)IPPROTO_TCP);
  891.         gen_and(b0, b1);
  892.         break;
  893.  
  894.     case Q_UDP:
  895.         b0 =  gen_linktype(ETHERTYPE_IP);
  896.         b1 = gen_cmp(off_nl + 9, BPF_B, (long)IPPROTO_UDP);
  897.         gen_and(b0, b1);
  898.         break;
  899.  
  900.     case Q_ICMP:
  901.         b0 =  gen_linktype(ETHERTYPE_IP);
  902.         b1 = gen_cmp(off_nl + 9, BPF_B, (long)IPPROTO_ICMP);
  903.         gen_and(b0, b1);
  904.         break;
  905.  
  906.     case Q_IP:
  907.         b1 =  gen_linktype(ETHERTYPE_IP);
  908.         break;
  909.  
  910.     case Q_ARP:
  911.         b1 =  gen_linktype(ETHERTYPE_ARP);
  912.         break;
  913.  
  914.     case Q_RARP:
  915.         b1 =  gen_linktype(ETHERTYPE_REVARP);
  916.         break;
  917.  
  918.     case Q_LINK:
  919.         bpf_error("link layer applied in wrong context");
  920.  
  921.     case Q_DECNET:
  922.         b1 =  gen_linktype(ETHERTYPE_DN);
  923.         break;
  924.  
  925.     case Q_LAT:
  926.         b1 =  gen_linktype(ETHERTYPE_LAT);
  927.         break;
  928.  
  929.     case Q_MOPDL:
  930.         b1 =  gen_linktype(ETHERTYPE_MOPDL);
  931.         break;
  932.  
  933.     case Q_MOPRC:
  934.         b1 =  gen_linktype(ETHERTYPE_MOPRC);
  935.         break;
  936.  
  937.     default:
  938.         abort();
  939.     }
  940.     return b1;
  941. }
  942.  
  943. static struct block *
  944. gen_ipfrag()
  945. {
  946.     struct slist *s;
  947.     struct block *b;
  948.  
  949.     /* not ip frag */
  950.     s = new_stmt(BPF_LD|BPF_H|BPF_ABS);
  951.     s->s.k = off_nl + 6;
  952.     b = new_block(JMP(BPF_JSET));
  953.     b->s.k = 0x1fff;
  954.     b->stmts = s;
  955.     gen_not(b);
  956.  
  957.     return b;
  958. }
  959.  
  960. static struct block *
  961. gen_portatom(off, v)
  962.     int off;
  963.     long v;
  964. {
  965.     struct slist *s;
  966.     struct block *b;
  967.  
  968.     s = new_stmt(BPF_LDX|BPF_MSH|BPF_B);
  969.     s->s.k = off_nl;
  970.  
  971.     s->next = new_stmt(BPF_LD|BPF_IND|BPF_H);
  972.     s->next->s.k = off_nl + off;
  973.  
  974.     b = new_block(JMP(BPF_JEQ));
  975.     b->stmts = s;
  976.     b->s.k = v;
  977.  
  978.     return b;
  979. }
  980.  
  981. struct block *
  982. gen_portop(port, proto, dir)
  983.     int port, proto, dir;
  984. {
  985.     struct block *b0, *b1, *tmp;
  986.  
  987.     /* ip proto 'proto' */
  988.     tmp = gen_cmp(off_nl + 9, BPF_B, (long)proto);
  989.     b0 = gen_ipfrag();
  990.     gen_and(tmp, b0);
  991.  
  992.     switch (dir) {
  993.     case Q_SRC:
  994.         b1 = gen_portatom(0, (long)port);
  995.         break;
  996.  
  997.     case Q_DST:
  998.         b1 = gen_portatom(2, (long)port);
  999.         break;
  1000.  
  1001.     case Q_OR:
  1002.     case Q_DEFAULT:
  1003.         tmp = gen_portatom(0, (long)port);
  1004.         b1 = gen_portatom(2, (long)port);
  1005.         gen_or(tmp, b1);
  1006.         break;
  1007.  
  1008.     case Q_AND:
  1009.         tmp = gen_portatom(0, (long)port);
  1010.         b1 = gen_portatom(2, (long)port);
  1011.         gen_and(tmp, b1);
  1012.         break;
  1013.  
  1014.     default:
  1015.         abort();
  1016.     }
  1017.     gen_and(b0, b1);
  1018.  
  1019.     return b1;
  1020. }
  1021.  
  1022. static struct block *
  1023. gen_port(port, ip_proto, dir)
  1024.     int port;
  1025.     int ip_proto;
  1026.     int dir;
  1027. {
  1028.     struct block *b0, *b1, *tmp;
  1029.  
  1030.     /* ether proto ip */
  1031.     b0 =  gen_linktype(ETHERTYPE_IP);
  1032.  
  1033.     switch (ip_proto) {
  1034.     case IPPROTO_UDP:
  1035.     case IPPROTO_TCP:
  1036.         b1 = gen_portop(port, ip_proto, dir);
  1037.         break;
  1038.  
  1039.     case PROTO_UNDEF:
  1040.         tmp = gen_portop(port, IPPROTO_TCP, dir);
  1041.         b1 = gen_portop(port, IPPROTO_UDP, dir);
  1042.         gen_or(tmp, b1);
  1043.         break;
  1044.  
  1045.     default:
  1046.         abort();
  1047.     }
  1048.     gen_and(b0, b1);
  1049.     return b1;
  1050. }
  1051.  
  1052. static int
  1053. lookup_proto(name, proto)
  1054.     char *name;
  1055.     int proto;
  1056. {
  1057.     int v;
  1058.  
  1059.     switch (proto) {
  1060.     case Q_DEFAULT:
  1061.     case Q_IP:
  1062.         v = pcap_nametoproto(name);
  1063.         if (v == PROTO_UNDEF)
  1064.             bpf_error("unknown ip proto '%s'", name);
  1065.         break;
  1066.  
  1067.     case Q_LINK:
  1068.         /* XXX should look up h/w protocol type based on linktype */
  1069.         v = pcap_nametoeproto(name);
  1070.         if (v == PROTO_UNDEF)
  1071.             bpf_error("unknown ether proto '%s'", name);
  1072.         break;
  1073.  
  1074.     default:
  1075.         v = PROTO_UNDEF;
  1076.         break;
  1077.     }
  1078.     return v;
  1079. }
  1080.  
  1081. static struct block *
  1082. gen_proto(v, proto, dir)
  1083.     int v;
  1084.     int proto;
  1085.     int dir;
  1086. {
  1087.     struct block *b0, *b1;
  1088.  
  1089.     if (dir != Q_DEFAULT)
  1090.         bpf_error("direction applied to 'proto'");
  1091.  
  1092.     switch (proto) {
  1093.     case Q_DEFAULT:
  1094.     case Q_IP:
  1095.         b0 = gen_linktype(ETHERTYPE_IP);
  1096.         b1 = gen_cmp(off_nl + 9, BPF_B, (long)v);
  1097.         gen_and(b0, b1);
  1098.         return b1;
  1099.  
  1100.     case Q_ARP:
  1101.         bpf_error("arp does not encapsulate another protocol");
  1102.         /* NOTREACHED */
  1103.  
  1104.     case Q_RARP:
  1105.         bpf_error("rarp does not encapsulate another protocol");
  1106.         /* NOTREACHED */
  1107.  
  1108.     case Q_DECNET:
  1109.         bpf_error("decnet encapsulation is not specifiable");
  1110.         /* NOTREACHED */
  1111.  
  1112.     case Q_LAT:
  1113.         bpf_error("lat does not encapsulate another protocol");
  1114.         /* NOTREACHED */
  1115.  
  1116.     case Q_MOPRC:
  1117.         bpf_error("moprc does not encapsulate another protocol");
  1118.         /* NOTREACHED */
  1119.  
  1120.     case Q_MOPDL:
  1121.         bpf_error("mopdl does not encapsulate another protocol");
  1122.         /* NOTREACHED */
  1123.  
  1124.     case Q_LINK:
  1125.         return gen_linktype(v);
  1126.  
  1127.     case Q_UDP:
  1128.         bpf_error("'udp proto' is bogus");
  1129.         /* NOTREACHED */
  1130.  
  1131.     case Q_TCP:
  1132.         bpf_error("'tcp proto' is bogus");
  1133.         /* NOTREACHED */
  1134.  
  1135.     case Q_ICMP:
  1136.         bpf_error("'icmp proto' is bogus");
  1137.         /* NOTREACHED */
  1138.  
  1139.     default:
  1140.         abort();
  1141.         /* NOTREACHED */
  1142.     }
  1143.     /* NOTREACHED */
  1144. }
  1145.  
  1146. /*
  1147.  * Left justify 'addr' and return its resulting network mask.
  1148.  */
  1149. static u_long
  1150. net_mask(addr)
  1151.     u_long *addr;
  1152. {
  1153.     register u_long m = 0xffffffff;
  1154.  
  1155.     if (*addr)
  1156.         while ((*addr & 0xff000000) == 0)
  1157.             *addr <<= 8, m <<= 8;
  1158.  
  1159.     return m;
  1160. }
  1161.  
  1162. struct block *
  1163. gen_scode(name, q)
  1164.     char *name;
  1165.     struct qual q;
  1166. {
  1167.     int proto = q.proto;
  1168.     int dir = q.dir;
  1169.     u_char *eaddr;
  1170.     u_long mask, addr, **alist;
  1171.     struct block *b, *tmp;
  1172.     int port, real_proto;
  1173.  
  1174.     switch (q.addr) {
  1175.  
  1176.     case Q_NET:
  1177.         addr = pcap_nametonetaddr(name);
  1178.         if (addr == 0)
  1179.             bpf_error("unknown network '%s'", name);
  1180.         mask = net_mask(&addr);
  1181.         return gen_host(addr, mask, proto, dir);
  1182.  
  1183.     case Q_DEFAULT:
  1184.     case Q_HOST:
  1185.         if (proto == Q_LINK) {
  1186.             switch (linktype) {
  1187.             case DLT_EN10MB:
  1188.                 eaddr = pcap_ether_hostton(name);
  1189.                 if (eaddr == NULL)
  1190.                     bpf_error("unknown ether host '%s'", name);
  1191.                 return gen_ehostop(eaddr, dir);
  1192.  
  1193. #ifdef FDDI
  1194.             case DLT_FDDI:
  1195.                 eaddr = pcap_ether_hostton(name);
  1196.                 if (eaddr == NULL)
  1197.                     bpf_error("unknown FDDI host '%s'", name);
  1198.                 return gen_fhostop(eaddr, dir);
  1199. #endif
  1200.             default:
  1201.                 bpf_error("only ethernet/FDDI supports link-level host name");
  1202.                 break;
  1203.             }
  1204.         } else if (proto == Q_DECNET) {
  1205.             unsigned short dn_addr = __pcap_nametodnaddr(name);
  1206.             /*
  1207.              * I don't think DECNET hosts can be multihomed, so
  1208.              * there is no need to build up a list of addresses
  1209.              */
  1210.             return (gen_host(dn_addr, 0, proto, dir));
  1211.         } else {
  1212.             alist = pcap_nametoaddr(name);
  1213.             if (alist == NULL || *alist == NULL)
  1214.                 bpf_error("unknown host '%s'", name);
  1215.             b = gen_host(**alist++, 0xffffffffL, proto, dir);
  1216.             while (*alist) {
  1217.                 tmp = gen_host(**alist++, 0xffffffffL,
  1218.                            proto, dir);
  1219.                 gen_or(b, tmp);
  1220.                 b = tmp;
  1221.             }
  1222.             return b;
  1223.         }
  1224.  
  1225.     case Q_PORT:
  1226.         if (proto != Q_DEFAULT && proto != Q_UDP && proto != Q_TCP)
  1227.             bpf_error("illegal qualifier of 'port'");
  1228.         if (pcap_nametoport(name, &port, &real_proto) == 0)
  1229.             bpf_error("unknown port '%s'", name);
  1230.         if (proto == Q_UDP) {
  1231.             if (real_proto == IPPROTO_TCP)
  1232.                 bpf_error("port '%s' is tcp", name);
  1233.             else
  1234.                 /* override PROTO_UNDEF */
  1235.                 real_proto = IPPROTO_UDP;
  1236.         }
  1237.         if (proto == Q_TCP) {
  1238.             if (real_proto == IPPROTO_UDP)
  1239.                 bpf_error("port '%s' is udp", name);
  1240.             else
  1241.                 /* override PROTO_UNDEF */
  1242.                 real_proto = IPPROTO_TCP;
  1243.         }
  1244.         return gen_port(port, real_proto, dir);
  1245.  
  1246.     case Q_GATEWAY:
  1247.         eaddr = pcap_ether_hostton(name);
  1248.         if (eaddr == NULL)
  1249.             bpf_error("unknown ether host: %s", name);
  1250.  
  1251.         alist = pcap_nametoaddr(name);
  1252.         if (alist == NULL || *alist == NULL)
  1253.             bpf_error("unknown host '%s'", name);
  1254.         return gen_gateway(eaddr, alist, proto, dir);
  1255.  
  1256.     case Q_PROTO:
  1257.         real_proto = lookup_proto(name, proto);
  1258.         if (real_proto >= 0)
  1259.             return gen_proto(real_proto, proto, dir);
  1260.         else
  1261.             bpf_error("unknown protocol: %s", name);
  1262.  
  1263.     case Q_UNDEF:
  1264.         syntax();
  1265.         /* NOTREACHED */
  1266.     }
  1267.     abort();
  1268.     /* NOTREACHED */
  1269. }
  1270.  
  1271. struct block *
  1272. gen_ncode(v, q)
  1273.     u_long v;
  1274.     struct qual q;
  1275. {
  1276.     u_long mask;
  1277.     int proto = q.proto;
  1278.     int dir = q.dir;
  1279.  
  1280.     switch (q.addr) {
  1281.  
  1282.     case Q_DEFAULT:
  1283.     case Q_HOST:
  1284.     case Q_NET:
  1285.         if (proto == Q_DECNET)
  1286.             return gen_host(v, 0, proto, dir);
  1287.         else if (proto == Q_LINK) {
  1288.             bpf_error("illegal link layer address");
  1289.         } else {
  1290.             mask = net_mask(&v);
  1291.             return gen_host(v, mask, proto, dir);
  1292.         }
  1293.  
  1294.     case Q_PORT:
  1295.         if (proto == Q_UDP)
  1296.             proto = IPPROTO_UDP;
  1297.         else if (proto == Q_TCP)
  1298.             proto = IPPROTO_TCP;
  1299.         else if (proto == Q_DEFAULT)
  1300.             proto = PROTO_UNDEF;
  1301.         else
  1302.             bpf_error("illegal qualifier of 'port'");
  1303.  
  1304.         return gen_port((int)v, proto, dir);
  1305.  
  1306.     case Q_GATEWAY:
  1307.         bpf_error("'gateway' requires a name");
  1308.         /* NOTREACHED */
  1309.  
  1310.     case Q_PROTO:
  1311.         return gen_proto((int)v, proto, dir);
  1312.  
  1313.     case Q_UNDEF:
  1314.         syntax();
  1315.         /* NOTREACHED */
  1316.  
  1317.     default:
  1318.         abort();
  1319.         /* NOTREACHED */
  1320.     }
  1321.     /* NOTREACHED */
  1322. }
  1323.  
  1324. struct block *
  1325. gen_ecode(eaddr, q)
  1326.     u_char *eaddr;
  1327.     struct qual q;
  1328. {
  1329.     if ((q.addr == Q_HOST || q.addr == Q_DEFAULT) && q.proto == Q_LINK) {
  1330.         if (linktype == DLT_EN10MB)
  1331.             return gen_ehostop(eaddr, (int)q.dir);
  1332. #ifdef FDDI
  1333.         if (linktype == DLT_FDDI)
  1334.             return gen_fhostop(eaddr, (int)q.dir);
  1335. #endif
  1336.     }
  1337.     bpf_error("ethernet address used in non-ether expression");
  1338.     /* NOTREACHED */
  1339. }
  1340.  
  1341. void
  1342. sappend(s0, s1)
  1343.     struct slist *s0, *s1;
  1344. {
  1345.     /*
  1346.      * This is definitely not the best way to do this, but the
  1347.      * lists will rarely get long.
  1348.      */
  1349.     while (s0->next)
  1350.         s0 = s0->next;
  1351.     s0->next = s1;
  1352. }
  1353.  
  1354. static struct slist *
  1355. xfer_to_x(a)
  1356.     struct arth *a;
  1357. {
  1358.     struct slist *s;
  1359.  
  1360.     s = new_stmt(BPF_LDX|BPF_MEM);
  1361.     s->s.k = a->regno;
  1362.     return s;
  1363. }
  1364.  
  1365. static struct slist *
  1366. xfer_to_a(a)
  1367.     struct arth *a;
  1368. {
  1369.     struct slist *s;
  1370.  
  1371.     s = new_stmt(BPF_LD|BPF_MEM);
  1372.     s->s.k = a->regno;
  1373.     return s;
  1374. }
  1375.  
  1376. struct arth *
  1377. gen_load(proto, index, size)
  1378.     int proto;
  1379.     struct arth *index;
  1380.     int size;
  1381. {
  1382.     struct slist *s, *tmp;
  1383.     struct block *b;
  1384.     int regno = alloc_reg();
  1385.  
  1386.     free_reg(index->regno);
  1387.     switch (size) {
  1388.  
  1389.     default:
  1390.         bpf_error("data size must be 1, 2, or 4");
  1391.  
  1392.     case 1:
  1393.         size = BPF_B;
  1394.         break;
  1395.  
  1396.     case 2:
  1397.         size = BPF_H;
  1398.         break;
  1399.  
  1400.     case 4:
  1401.         size = BPF_W;
  1402.         break;
  1403.     }
  1404.     switch (proto) {
  1405.     default:
  1406.         bpf_error("unsupported index operation");
  1407.  
  1408.     case Q_LINK:
  1409.         s = xfer_to_x(index);
  1410.         tmp = new_stmt(BPF_LD|BPF_IND|size);
  1411.         sappend(s, tmp);
  1412.         sappend(index->s, s);
  1413.         break;
  1414.  
  1415.     case Q_IP:
  1416.     case Q_ARP:
  1417.     case Q_RARP:
  1418.     case Q_DECNET:
  1419.     case Q_LAT:
  1420.     case Q_MOPRC:
  1421.     case Q_MOPDL:
  1422.         /* XXX Note that we assume a fixed link link header here. */
  1423.         s = xfer_to_x(index);
  1424.         tmp = new_stmt(BPF_LD|BPF_IND|size);
  1425.         tmp->s.k = off_nl;
  1426.         sappend(s, tmp);
  1427.         sappend(index->s, s);
  1428.  
  1429.         b = gen_proto_abbrev(proto);
  1430.         if (index->b)
  1431.             gen_and(index->b, b);
  1432.         index->b = b;
  1433.         break;
  1434.  
  1435.     case Q_TCP:
  1436.     case Q_UDP:
  1437.     case Q_ICMP:
  1438.         s = new_stmt(BPF_LDX|BPF_MSH|BPF_B);
  1439.         s->s.k = off_nl;
  1440.         sappend(s, xfer_to_a(index));
  1441.         sappend(s, new_stmt(BPF_ALU|BPF_ADD|BPF_X));
  1442.         sappend(s, new_stmt(BPF_MISC|BPF_TAX));
  1443.         sappend(s, tmp = new_stmt(BPF_LD|BPF_IND|size));
  1444.         tmp->s.k = off_nl;
  1445.         sappend(index->s, s);
  1446.  
  1447.         gen_and(gen_proto_abbrev(proto), b = gen_ipfrag());
  1448.         if (index->b)
  1449.             gen_and(index->b, b);
  1450.         index->b = b;
  1451.         break;
  1452.     }
  1453.     index->regno = regno;
  1454.     s = new_stmt(BPF_ST);
  1455.     s->s.k = regno;
  1456.     sappend(index->s, s);
  1457.  
  1458.     return index;
  1459. }
  1460.  
  1461. struct block *
  1462. gen_relation(code, a0, a1, reversed)
  1463.     int code;
  1464.     struct arth *a0, *a1;
  1465.     int reversed;
  1466. {
  1467.     struct slist *s0, *s1, *s2;
  1468.     struct block *b, *tmp;
  1469.  
  1470.     s0 = xfer_to_x(a1);
  1471.     s1 = xfer_to_a(a0);
  1472.     s2 = new_stmt(BPF_ALU|BPF_SUB|BPF_X);
  1473.     b = new_block(JMP(code));
  1474.     if (reversed)
  1475.         gen_not(b);
  1476.  
  1477.     sappend(s1, s2);
  1478.     sappend(s0, s1);
  1479.     sappend(a1->s, s0);
  1480.     sappend(a0->s, a1->s);
  1481.  
  1482.     b->stmts = a0->s;
  1483.  
  1484.     free_reg(a0->regno);
  1485.     free_reg(a1->regno);
  1486.  
  1487.     /* 'and' together protocol checks */
  1488.     if (a0->b) {
  1489.         if (a1->b) {
  1490.             gen_and(a0->b, tmp = a1->b);
  1491.         }
  1492.         else
  1493.             tmp = a0->b;
  1494.     } else
  1495.         tmp = a1->b;
  1496.  
  1497.     if (tmp)
  1498.         gen_and(tmp, b);
  1499.  
  1500.     return b;
  1501. }
  1502.  
  1503. struct arth *
  1504. gen_loadlen()
  1505. {
  1506.     int regno = alloc_reg();
  1507.     struct arth *a = (struct arth *)newchunk(sizeof(*a));
  1508.     struct slist *s;
  1509.  
  1510.     s = new_stmt(BPF_LD|BPF_LEN);
  1511.     s->next = new_stmt(BPF_ST);
  1512.     s->next->s.k = regno;
  1513.     a->s = s;
  1514.     a->regno = regno;
  1515.  
  1516.     return a;
  1517. }
  1518.  
  1519. struct arth *
  1520. gen_loadi(val)
  1521.     int val;
  1522. {
  1523.     struct arth *a;
  1524.     struct slist *s;
  1525.     int reg;
  1526.  
  1527.     a = (struct arth *)newchunk(sizeof(*a));
  1528.  
  1529.     reg = alloc_reg();
  1530.  
  1531.     s = new_stmt(BPF_LD|BPF_IMM);
  1532.     s->s.k = val;
  1533.     s->next = new_stmt(BPF_ST);
  1534.     s->next->s.k = reg;
  1535.     a->s = s;
  1536.     a->regno = reg;
  1537.  
  1538.     return a;
  1539. }
  1540.  
  1541. struct arth *
  1542. gen_neg(a)
  1543.     struct arth *a;
  1544. {
  1545.     struct slist *s;
  1546.  
  1547.     s = xfer_to_a(a);
  1548.     sappend(a->s, s);
  1549.     s = new_stmt(BPF_ALU|BPF_NEG);
  1550.     s->s.k = 0;
  1551.     sappend(a->s, s);
  1552.     s = new_stmt(BPF_ST);
  1553.     s->s.k = a->regno;
  1554.     sappend(a->s, s);
  1555.  
  1556.     return a;
  1557. }
  1558.  
  1559. struct arth *
  1560. gen_arth(code, a0, a1)
  1561.     int code;
  1562.     struct arth *a0, *a1;
  1563. {
  1564.     struct slist *s0, *s1, *s2;
  1565.  
  1566.     s0 = xfer_to_x(a1);
  1567.     s1 = xfer_to_a(a0);
  1568.     s2 = new_stmt(BPF_ALU|BPF_X|code);
  1569.  
  1570.     sappend(s1, s2);
  1571.     sappend(s0, s1);
  1572.     sappend(a1->s, s0);
  1573.     sappend(a0->s, a1->s);
  1574.  
  1575.     free_reg(a1->regno);
  1576.  
  1577.     s0 = new_stmt(BPF_ST);
  1578.     a0->regno = s0->s.k = alloc_reg();
  1579.     sappend(a0->s, s0);
  1580.  
  1581.     return a0;
  1582. }
  1583.  
  1584. /*
  1585.  * Here we handle simple allocation of the scratch registers.
  1586.  * If too many registers are alloc'd, the allocator punts.
  1587.  */
  1588. static int regused[BPF_MEMWORDS];
  1589. static int curreg;
  1590.  
  1591. /*
  1592.  * Return the next free register.
  1593.  */
  1594. static int
  1595. alloc_reg()
  1596. {
  1597.     int n = BPF_MEMWORDS;
  1598.  
  1599.     while (--n >= 0) {
  1600.         if (regused[curreg])
  1601.             curreg = (curreg + 1) % BPF_MEMWORDS;
  1602.         else {
  1603.             regused[curreg] = 1;
  1604.             return curreg;
  1605.         }
  1606.     }
  1607.     bpf_error("too many registers needed to evaluate expression");
  1608.     /* NOTREACHED */
  1609. }
  1610.  
  1611. /*
  1612.  * Return a register to the table so it can
  1613.  * be used later.
  1614.  */
  1615. static void
  1616. free_reg(n)
  1617.     int n;
  1618. {
  1619.     regused[n] = 0;
  1620. }
  1621.  
  1622. static struct block *
  1623. gen_len(jmp, n)
  1624.     int jmp, n;
  1625. {
  1626.     struct slist *s;
  1627.     struct block *b;
  1628.  
  1629.     s = new_stmt(BPF_LD|BPF_LEN);
  1630.     s->next = new_stmt(BPF_ALU|BPF_SUB|BPF_K);
  1631.     s->next->s.k = n;
  1632.     b = new_block(JMP(jmp));
  1633.     b->stmts = s;
  1634.  
  1635.     return b;
  1636. }
  1637.  
  1638. struct block *
  1639. gen_greater(n)
  1640.     int n;
  1641. {
  1642.     return gen_len(BPF_JGE, n);
  1643. }
  1644.  
  1645. struct block *
  1646. gen_less(n)
  1647.     int n;
  1648. {
  1649.     struct block *b;
  1650.  
  1651.     b = gen_len(BPF_JGT, n);
  1652.     gen_not(b);
  1653.  
  1654.     return b;
  1655. }
  1656.  
  1657. struct block *
  1658. gen_byteop(op, idx, val)
  1659.     int op, idx, val;
  1660. {
  1661.     struct block *b;
  1662.     struct slist *s;
  1663.  
  1664.     switch (op) {
  1665.     default:
  1666.         abort();
  1667.  
  1668.     case '=':
  1669.         return gen_cmp((u_int)idx, BPF_B, (long)val);
  1670.  
  1671.     case '<':
  1672.         b = gen_cmp((u_int)idx, BPF_B, (long)val);
  1673.         b->s.code = JMP(BPF_JGE);
  1674.         gen_not(b);
  1675.         return b;
  1676.  
  1677.     case '>':
  1678.         b = gen_cmp((u_int)idx, BPF_B, (long)val);
  1679.         b->s.code = JMP(BPF_JGT);
  1680.         return b;
  1681.  
  1682.     case '|':
  1683.         s = new_stmt(BPF_ALU|BPF_OR|BPF_K);
  1684.         break;
  1685.  
  1686.     case '&':
  1687.         s = new_stmt(BPF_ALU|BPF_AND|BPF_K);
  1688.         break;
  1689.     }
  1690.     s->s.k = val;
  1691.     b = new_block(JMP(BPF_JEQ));
  1692.     b->stmts = s;
  1693.     gen_not(b);
  1694.  
  1695.     return b;
  1696. }
  1697.  
  1698. struct block *
  1699. gen_broadcast(proto)
  1700.     int proto;
  1701. {
  1702.     u_long hostmask;
  1703.     struct block *b0, *b1, *b2;
  1704.     static u_char ebroadcast[] = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };
  1705.  
  1706.     switch (proto) {
  1707.  
  1708.     case Q_DEFAULT:
  1709.     case Q_LINK:
  1710.         if (linktype == DLT_EN10MB)
  1711.             return gen_ehostop(ebroadcast, Q_DST);
  1712. #ifdef FDDI
  1713.         if (linktype == DLT_FDDI)
  1714.             return gen_fhostop(ebroadcast, Q_DST);
  1715. #endif
  1716.         bpf_error("not a broadcast link");
  1717.         break;
  1718.  
  1719.     case Q_IP:
  1720.         b0 = gen_linktype(ETHERTYPE_IP);
  1721.         hostmask = ~netmask;
  1722.         b1 = gen_mcmp(off_nl + 16, BPF_W, (long)0, hostmask);
  1723.         b2 = gen_mcmp(off_nl + 16, BPF_W,
  1724.                   (long)(~0 & hostmask), hostmask);
  1725.         gen_or(b1, b2);
  1726.         gen_and(b0, b2);
  1727.         return b2;
  1728.     }
  1729.     bpf_error("only ether/ip broadcast filters supported");
  1730. }
  1731.  
  1732. struct block *
  1733. gen_multicast(proto)
  1734.     int proto;
  1735. {
  1736.     register struct block *b0, *b1;
  1737.     register struct slist *s;
  1738.  
  1739.     switch (proto) {
  1740.  
  1741.     case Q_DEFAULT:
  1742.     case Q_LINK:
  1743.         if (linktype == DLT_EN10MB) {
  1744.             /* ether[0] & 1 != 0 */
  1745.             s = new_stmt(BPF_LD|BPF_B|BPF_ABS);
  1746.             s->s.k = 0;
  1747.             b0 = new_block(JMP(BPF_JSET));
  1748.             b0->s.k = 1;
  1749.             b0->stmts = s;
  1750.             return b0;
  1751.         }
  1752.  
  1753.         if (linktype == DLT_FDDI) {
  1754.             /* XXX TEST THIS: MIGHT NOT PORT PROPERLY XXX */
  1755.             /* fddi[1] & 1 != 0 */
  1756.             s = new_stmt(BPF_LD|BPF_B|BPF_ABS);
  1757.             s->s.k = 1;
  1758.             b0 = new_block(JMP(BPF_JSET));
  1759.             b0->s.k = 1;
  1760.             b0->stmts = s;
  1761.             return b0;
  1762.         }
  1763.         /* Link not known to support multicasts */
  1764.         break;
  1765.  
  1766.     case Q_IP:
  1767.         b0 = gen_linktype(ETHERTYPE_IP);
  1768.         b1 = gen_cmp(off_nl + 16, BPF_B, (long)224);
  1769.         b1->s.code = JMP(BPF_JGE);
  1770.         gen_and(b0, b1);
  1771.         return b1;
  1772.     }
  1773.     bpf_error("only IP multicast filters supported on ethernet/FDDI");
  1774. }
  1775.  
  1776. /*
  1777.  * generate command for inbound/outbound.  It's here so we can
  1778.  * make it link-type specific.  'dir' = 0 implies "inbound",
  1779.  * = 1 implies "outbound".
  1780.  */
  1781. struct block *
  1782. gen_inbound(dir)
  1783.     int dir;
  1784. {
  1785.     register struct block *b0;
  1786.  
  1787.     b0 = gen_relation(BPF_JEQ,
  1788.               gen_load(Q_LINK, gen_loadi(0), 1),
  1789.               gen_loadi(0),
  1790.               dir);
  1791.     return (b0);
  1792. }
  1793.